package baseclass.i_GreedyStrategy;

import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * 一些项目要占用一个会议室宣讲， 会议室不能同时容纳两个项目的宣讲。
 * 给你每一个项目开始的时间和结束的时间(给你一个数组，里面是一个个具体的项目)，
 * 你来安排宣讲的日程，要求会议室进行 的宣讲的场次最多。返回这个最多的宣讲场次。
 * 注意：每场宣讲会中间可以间歇若干时间也可以用，只需要在代码中currentTime = program.end + interval即可
 * <p>
 * 1、按照宣讲会最早开始贪心，不行。一个可能持续一天
 * 2、按照宣讲会最短开始贪心，不行。因为某个宣讲会可能卡在两个宣讲会中
 *
 * @date 2020/3/1 13:42
 */

public class BestAverage {
    static class Program {
        int begin;
        int end;
        public Program(int begin, int end) {
            this.begin = begin;
            this.end = end;
        }
    }

    /**
     * 方法1：排序然后使用数组
     * @param current 当前时刻
     */
    public static int bestCount1(Program[] programs, int interval, int current) {
        if (programs == null || programs.length == 0) return 0;
        Arrays.sort(programs, (p1, p2) -> p1.end - p2.end);
        int res = 0;
        for (int i = 0; i < programs.length; i++) {
            if (current < programs[i].begin) {
                res++;
                current = programs[i].end;
            }
        }
        return res;
    }

    /**
     * 方法2：使用小跟堆
     *
     * @param current 当前时刻
     */
    public static int bestCount2(Program[] programs, int interval, int current) {
        if (programs == null || programs.length == 0) return 0;
        //小跟堆，存放会议结束时间
        Queue<Program> minQ = new PriorityQueue<>((p1, p2) -> p1.end - p2.end);
        for (Program program : programs) {
            minQ.add(program);
        }
        int res = 0;
        while (true) {
            //比如会议8点结束，那么小跟堆中 会议开始在8点前的都不要
            while (!minQ.isEmpty() && current > minQ.peek().begin)
                minQ.poll();
            if (minQ.isEmpty()) break;
            //当前会议结束时间
            current = minQ.poll().end;
            res++;

        }
        return res;
    }
}
